As electronic signal processing systems become more complex, engineers are continually faced with tradeoffs between performance, power and area (PPA) when implementing the numerical algorithms needed for a given system implementation. In many of these systems (e.g., communication systems, imaging systems, control systems, etc.), there is generally a need for more numerically efficient algorithms for computing mathematical values. If a given design involves fewer computations than another design to achieve the same numerical performance (e.g., accuracy), then such a design will require less area and power to produce the same desired numerical value. As a result, a design sensitive to PPA is better than another design from a system design perspective.
A variety of methods are known for computing mathematical functions such as magnitude and square root. For example, the cordic algorithm provides an iterative approach using a divide by two architecture. While the cordic algorithm can achieve N bits of precision in N iterations, the cordic algorithm is best suited for implementations that do not contain a multiplier.
Another approach to approximate the numerical value of mathematical functions is Newton-Raphson. The general mathematical representation of the Newton-Raphson approach for a mathematical function f(x) of a variable x is given by the following equation:
                              x                      n            +            1                          =                              x            n                    -                                    g              ⁡                              (                                  x                  n                                )                                                                    g                ′                            ⁡                              (                                  x                  n                                )                                                                        (        1        )            where g(x)=f(x)+b. For the Newton-Raphson approach, the derivative of the function f(x) must exist and have a finite value throughout the region of interest. Otherwise, the iterative approach will diverge from the desired result. The convergence of the Newton-Raphson method is quadratic in nature. That is, the number of accurate bits in the computation result roughly doubles for each iteration of the algorithm, assuming that the initial guess, x0, is close to the actual numerical result.
Another approach to approximate the numerical value of mathematical functions is the Taylor series. In mathematics, the Taylor series is known to be a representation of a function f(x) as an infinite sum of terms calculated from the values of its derivatives evaluated at a particular single point/value generally represented by an operating point a. The general mathematical representation of a Taylor series approximation for the numerical value of f(x) near an operating point a is given by the following equation:
                              f          ⁡                      (            x            )                          ≈                              ∑                          n              =              0                        ∞                    ⁢                                                                      f                                      (                    n                    )                                                  ⁡                                  (                  a                  )                                                            n                !                                      ⁢                                          (                                  x                  -                  a                                )                            n                                                          (        2        )            where f(n)(a) denotes the nth derivative of the function f(x) evaluated at the operating point a. In a practical application, the infinite sum in (2) is replaced with a finite sum of N terms as given by the following equation:
                              f          ⁡                      (            x            )                          ≈                              ∑                          n              =              0                                      N              -              1                                ⁢                                                                      f                                      (                    n                    )                                                  ⁡                                  (                  a                  )                                                            n                !                                      ⁢                                          (                                  x                  -                  a                                )                            n                                                          (        3        )            The accuracy of the numerical result can be determined directly from the number of terms N in the Taylor series approximation. That is, the bound for the error (e) can be written as:
                    e        =                                                                        f                ⁡                                  (                  x                  )                                            -                                                f                  ^                                ⁡                                  (                  x                  )                                                                          ≤                                                    f                                  (                  N                  )                                                            N                !                                      ⁢                                          (                                  x                  -                  a                                )                            N                                                          (        4        )            for an N term approximation. As a result, the number of terms needed for a given direct Taylor series design implementation will be determined by the numerical accuracy requirements of the system implementation. For reference, a conventional direct Taylor series implementation requires N*(N−1)/2 multiplications for an N term approximation.